package org.example.myleet.p763;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * https://leetcode-cn.com/problems/partition-labels/
 *
 * 此答案自己写的，13ms，38.6MB
 */
class Solution {

    private static final int MAX_PARTITION = 28;

    public List<Integer> partitionLabels(String S) {
        if (0 == S.length()) {
            return new ArrayList<>();
        }
        //每一段里面包含的字母集合
        List<Set<Character>> partitionCharacterSets = new ArrayList<>(MAX_PARTITION);
        //片段字母集合初始化
        for (int i=0; i<MAX_PARTITION; i++) {
            partitionCharacterSets.add(i, new HashSet<>());
        }
        //左开右闭的分割点列表
        int[] partitionPoints = new int[MAX_PARTITION];
        int sIdx = 0, partitionIdx = 1;
        //第一个字母先处理一次
        partitionCharacterSets.get(partitionIdx).add(S.charAt(sIdx));
        //因为左开，所以第一个分割点记录的位置应该是0的左边即-1
        partitionPoints[0] = -1;
        partitionPoints[partitionIdx] = sIdx;
        ++sIdx;
        //处理后续的字母
        while (sIdx < S.length()) {
            //处理当前位置的字母
            char s = S.charAt(sIdx);
            boolean found = false;
            for (int i = 0; i <= partitionIdx; i++) {
                //对每一段进行处理
                if (partitionCharacterSets.get(i).contains(s)) {
                    found = true;
                    //某一段i包含了这个字母，则说明这一段i需要延伸到sIdx，i段之后直到最新段合并到i段
                    for (int j=i+1; j<=partitionIdx; j++) {
                        //从i到partitionIdx段的字母集合并
                        partitionCharacterSets.get(i).addAll(partitionCharacterSets.get(j));
                    }
                    //更新字母集合，i下一个分段清空
                    partitionCharacterSets.get(i+1).clear();
                    //将i段作为最新段
                    partitionIdx = i;
                    //第i段延伸到sIdx的位置
                    partitionPoints[i] = sIdx;
                    //i段下一段重置长度
                    partitionPoints[i+1] = 0;
                    break;
                }
            }
            if (!found) {
                //没有找到包含这个字母的段，说明这个字母可能在下一段，新建字母集合，新建分割点
                ++partitionIdx;
                partitionCharacterSets.get(partitionIdx).add(s);
                partitionPoints[partitionIdx] = sIdx;
            }
            ++sIdx;
        }
        List<Integer> result = new ArrayList<>(partitionIdx+1);
        //获得各分段长度
        for (int i=1; i<=partitionIdx; i++) {
            result.add(partitionPoints[i] - partitionPoints[i-1]);
        }
        return result;
    }
}
